package Solution101_200.problem102.BinaryTreeLevelOrderTraversal;

import common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/07/10 11:42
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        if(root==null){
            return result;
        }
        List<TreeNode> nodes=new ArrayList<>();
        nodes.add(root);
        travel(result,nodes);
        return result;
    }

    private void travel(List<List<Integer>> result,List<TreeNode> nodes){
        List<Integer> levelResult=new ArrayList<>();
        List<TreeNode> nextLevelNodes=new ArrayList<>();
        for(TreeNode node:nodes){
            levelResult.add(node.val);
            if(node.left!=null){
                nextLevelNodes.add(node.left);
            }
            if(node.right!=null){
                nextLevelNodes.add(node.right);
            }
        }
        result.add(levelResult);
        if(nextLevelNodes.size()==0){
            return;
        }
        travel(result,nextLevelNodes);
    }
}
